package algorithm.leetcode.medium;

/*
 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/3
 */
public class Question34 {

    public static void main(String[] args) {

    }

    public int[] searchRange(int[] nums, int target) {
        int index = search(nums, target);
        if (index == -1) {
            return new int[] {-1, -1};
        }
        int left = index - 1;
        int right = index + 1;
        while (left >= 0 && target == nums[left]) {
            left--;
        }
        while (right < nums.length && target == nums[right]) {
            right++;
        }
        return new int[]{left + 1, right - 1};
    }


    private int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (target == nums[mid]) {
                return mid;
            }else if (target > nums[mid]) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }



}
